其他
用 Python 实现十大经典排序算法
The following article is from Python数据之道 Author 我是阳哥
01冒泡排序
注:上图中,数字表示的是数据序列原始的索引号。
算法过程
比较相邻的元素,如果前一个比后一个大,就把它们两个对调位置。 对排序数组中每一对相邻元素做同样的工作,直到全部完成,此时最后的元素将会是本轮排序中最大的数。 对剩下的元素继续重复以上的步骤,直到没有任何一个元素需要比较。
算法特点
Python代码
n = len(lst)
for i in range(n):
for j in range(1, n - i):
if lst[j - 1] > lst[j]:
lst[j - 1], lst[j] = lst[j], lst[j - 1]
return lst
02选择排序
选择排序原理
Python代码
for i in range(len(lst) - 1):
min_index = i
for j in range(i + 1, len(lst)):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
03快速排序
算法过程
先从数据序列中取出一个数作为基准数(baseline,习惯取第一个数)。 分区过程,将比基准数小的数全放到它的左边,大于或等于它的数全放到它的右边。 再对左右区间递归(recursive)重复第二步,直到各区间只有一个数。
15
为基准数,将比 15
小的数放在左边,比 15
大(大于或等于)的数放在右边11
为基准数,将比 11
小的数放在左边,比 11
大(大于或等于)的数放在右边。Python代码
n = len(lst)
if n <= 1:
return lst
baseline = lst[0]
left = [lst[i] for i in range(1, len(lst)) if lst[i] < baseline]
right = [lst[i] for i in range(1, len(lst)) if lst[i] >= baseline]
return quick_sort(left) + [baseline] + quick_sort(right)
04归并排序
算法思想
算法流程
步骤1:进行序列拆分,一直拆分到只有一个元素; 步骤2:拆分完成后,开始递归合并。
图解算法
拆分
[15,11,13,18,10]
,我们从首先从数据序列的中间位置开始拆分,中间位置的设置为合并
Python代码
def merge(left,right):
i = 0
j = 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result = result + left[i:] + right[j:]
return result
n = len(lst)
if n <= 1:
return lst
mid = n // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left,right)
05堆排序
堆的定义
堆
:小顶堆
如下图所示:大顶堆
如下图所示:堆排序
。堆的存储
0
处, i
结点的父结点下标就为 (i-1)/2
。i
结点的左右子结点下标分别为 2*i+1
和 2*i+2
。堆排序
如何由一个无序序列建成一个堆?
如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?
堆的初始化
[n/2]
向下取整,所以筛选只需要从第 [n/2]
向下取整个元素开始,从后往前进行调整。进行堆排序
Python代码
def adjust_heap(lst, i, size):
left_index = 2 * i + 1
right_index = 2 * i + 2
largest_index = i
if left_index < size and lst[left_index] > lst[largest_index]:
largest_index = left_index
if right_index < size and lst[right_index] > lst[largest_index]:
largest_index = right_index
if largest_index != i:
lst[largest_index], lst[i] = lst[i], lst[largest_index]
adjust_heap(lst, largest_index, size)
def built_heap(lst, size):
for i in range(len(lst)//2)[::-1]:
adjust_heap(lst, i, size)
size = len(lst)
built_heap(lst, size)
for i in range(len(lst))[::-1]:
lst[0], lst[i] = lst[i], lst[0]
adjust_heap(lst, 0, i)
return lst
06插入排序
Python代码
for i in range(len(lst) - 1):
cur_num, pre_index = lst[i+1], i
while pre_index >= 0 and cur_num < lst[pre_index]:
lst[pre_index + 1] = lst[pre_index]
pre_index -= 1
lst[pre_index + 1] = cur_num
return lst
07希尔排序
基本原理
注:红色箭头标注的地方,是子序列内部排序后的状态
Python代码
n = len(lst)
gap = n // 2
while gap > 0:
for i in range(gap, n):
for j in range(i, gap - 1, -gap):
if lst[j] < lst[j - gap]:
lst[j], lst[j - gap] = lst[j - gap], lst[j]
else:
break
gap //= 2
return lst
08计数排序
基本原理
最大值-最小值+1
的数组;Python代码
nums_min = min(lst)
bucket = [0] * (max(lst) + 1 - nums_min)
for num in lst:
bucket[num - nums_min] += 1
i = 0
for j in range(len(bucket)):
while bucket[j] > 0:
lst[i] = j + nums_min
bucket[j] -= 1
i += 1
return lst
09桶排序
基本思想
桶的划分过程
defaultBucketSize = 10
),则第一个桶的范围为 10到20,第二个桶的数据范围是20到30,依次类推。最后,我们一共需要4个桶来放入数据。排序过程
defaultBucketSize = 20
),经计算,一共需要4个桶来放入数据。冒泡排序
来对桶内数据进行排序。Python代码
maxVal, minVal = max(lst), min(lst)
bucketSize = defaultBucketSize
bucketCount = (maxVal - minVal) // bucketSize + 1
buckets = [[] for i in range(bucketCount)]
for num in lst:
buckets[(num - minVal) // bucketSize].append(num)
lst.clear()
for bucket in buckets:
bubble_sort(bucket)
lst.extend(bucket)
return lst
10基数排序
基本思想
算法流程
Python代码
def radix_sort(lst):
mod = 10
div = 1
mostBit = len(str(max(lst)))
buckets = [[] for row in range(mod)]
while mostBit:
for num in lst:
buckets[num // div % mod].append(num)
i = 0
for bucket in buckets:
while bucket:
lst[i] = bucket.pop(0)
i += 1
div *= 10
mostBit -= 1
return lst
11小结
参考文档
https://www.jianshu.com/p/bbbab7fa77a2 https://blog.csdn.net/MakerCloud/article/details/86182145 https://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html https://www.cnblogs.com/jin-nuo/p/5293554.html
技术资讯
分享
点收藏
点点赞
点在看